1. Field of the Invention
The present invention relates to a method of determining a route from a starting point to a destination in a route network, especially a network of roads or streets, which is represented by a group of straight edges and nodes in a memory, in which each edge is correlated with a path resistance and the route is determined as a successive sequence of edges by minimizing the sum of all the path resistances.
2. Prior Art
In vehicles, such as motor vehicles, aircraft or ships, installed navigation systems guide the driver of the vehicle rapidly, reliably and easily to the desired destination, without the previous effort of planing a route and acquiring and studying map or chart materials. Navigation data is stored, for example on CD-ROM, in navigation systems, which includes appropriate data from charts, maps or road maps. The navigation apparatus, for example, uses GPS (Global Positioning System), in order to establish a momentary position and to compute appropriate navigation directions for guidance to a predetermined destination. The navigation data preferably includes data regarding streets and roads for a motor vehicle.
Suitable algorithms for route planning have been used in navigation systems, which compute an optimum route of travel from a starting point to a destination using stored navigation data together with the starting point and the destination. This sort of algorithm for route planning is based on the best path algorithms according to Ford and Moore, which are known from graph theory and are adjusted to the special requirements of self-sufficient vehicle navigation systems.
As is apparent from FIG. 1, the road network is represented by a route algorithm such as a graph with edges k and nodes p, for mathematical processing in which the edges correspond to roads or streets and the nodes correspond to intersections of the roads or road network. In FIG. 1 four edges k.sub.1, k.sub.2, k.sub.3 and k.sub.4 and four nodes p.sub.1, p.sub.2, p.sub.3 and p.sub.4 are provided. Since the traffic flow is directional in real road traffic, an edge k must be represented as a directional vector. Furthermore a resistance, the so-called path resistance, which is a variable representing the effort required to travel from one node in the network to another, is associated with each edge k. For example, the edge length is used as the path resistance. Alternatively the travel time along the edge can be used as the path resistance, thus including the average travel speed along the respective edge. In a further alternative embodiment a cost function is provided, which involves a weighted mixed computation of various properties, such as the edge length, travel time on an edge or the width of an edge (construction condition). Also a resistance is associated with the respective nodes, which reflects the cost of vehicle maneuvers (straight out, left/right deviations, turns, etc). All best path algorithms determine only a route between a starting edge and a destination edge on a directional graph with the property that the sum of all road resistances of the edges of the determined route and if necessary with the node resistance considered is minimized.
This sort of best path algorithm calculates the route by reverse iteration and tests all edges in the graph, evaluating them in relation to the best path to the destination road or edge. In other words, starting from the destination edge, in each iteration step a best path in regard to resistance back to the edges in the list which were optimized in the previous iteration step is determined. As a result the method provides an optimum route to the destination edge from each edge in the graph. A so-called route table for the calculated result is set up in the memory of the navigation device. This sort of route table is shown for example below for the graph shown in FIG. 1.
TABLE I ROUTE +Following -Following Edge +Resistance edge -Resistance edge K.sub.1 .infin. - .infin. - K.sub.2 .infin. - .infin. - K.sub.3 .infin. - .infin. - K.sub.4 .infin. - .infin. -
For each edge in the graph the resistance to the destination edge in the graph and the edge following in the destination direction are given. The resistance is given an "infinite" value (symbol .infin.) and the following edge is set as "undefined" (symbol -) as respective initial values. A positive sign in the resistance and following edge columns stands for consideration of the respective edge in its arrow direction, whereas a negative sign stands for consideration of the respective edge opposite to its arrow direction.
Before the start of the iterative optimization the destination edge in the route table is initialized (see above) with a null resistance. As an example the edge k.sub.3 is selected to be that destination edge. The following stored route table II results from a destination initialization.
TABLE II ROUTE +Following -Following Edge +Resistance edge -Resistance edge K.sub.1 .infin. - .infin. - K.sub.2 .infin. - .infin. - K.sub.3 0 - 0 - K.sub.4 .infin. - .infin. -
Furthermore the destination edge k.sub.3 is added to a list stored in the navigation device of the already optimized edges, so that a list of the already optimized edges according to the following list 1 results. ##STR1##
Furthermore a second list of the edges to be tested in the next optimization step is provided, which is empty at the start of the method, according to the following list I. ##STR2##
The method now starts, since it consider all edges listed in List I as fixed actual positions of the vehicle and all edges interconnected with this "actual-edge", the so-called "incoming-edges", participating in the optimization. In the exemplary embodiment (FIG. 1) the edges interconnected with the "actual-edge" read +k.sub.2, -k.sub.3 and -k.sub.4. In the optimization testing now the resistance of a respective incoming-edge is compared with the resistance to the destination that the incoming-edge would have when it leads to the destination over the actual-edge. At this point a so-called resistance optimization condition is set forth: EQU Resistance(incoming edge)&gt;path resistance (incoming-edge)+Resistance(actual edge).
Here "resistance" represents the resistance added into the route table and "path resistance" represents a path resistance associated with a respective edge in the graph. When this resistance optimization condition is fulfilled, the resistance of the incoming-edge in the route table is replaced by the new smaller value, the actual-edge is entered as the following edge and the optimized incoming edge is input to the list II. If all edges from the list 1, as already described, are processed, the list I and list II are interchanged and subsequently the list 2 is empty. The process ends when list 1 is found to be empty.
Subsequently this process will be explained in more detailed using the road network according to FIG. 1. In this embodiment the edges k.sub.1, k.sub.2 and k.sub.3 have the path resistance 10 and the edge k.sub.4 has the path resistance 30. Sine the sol-called turning resistance is not of significance for this process, it remains unconsidered in the present example. In step 1 the actual-edge is set equal to +k.sub.3 and the list I is as follows: ##STR3##
Now all incoming-edges for +k.sub.3 are tested with the resistance optimization conditions, as illustrated in FIG. 2. The resistance optimization conditions results:
-k.sub.3 0&gt;10+0 resistance optimization condition not fulfilled PA1 +k.sub.2 .infin.&gt;10+0 resistance optimization condition fulfilled PA1 -k.sub.4 .infin.&gt;30+0 resistance optimization conduction fulfilled. PA1 (1) setting up a route table in which a respective resistance value, following edge value and traffic-way-type value are entered for each straight edge in a forward direction and in a back direction; PA1 (2) setting all resistance values and all traffic-way-type values of the route table to infinity and clearing all following edge values; PA1 (3) setting the resistance value and traffic-way-type value of the destination edge to zero; PA1 (4) storing the destination edge in a first list for already optimized edges; PA1 (5) setting up of an empty second list for edges to be optimized in the next step; PA1 (6) determining whether or not the first list is empty, and if a positive result is obtained the method is halted; PA1 (7) picking an edge from the first list as the actual edge; PA1 (8) defining all edges interconnected with the actual edge as incoming edges; PA1 (9) determining for all incoming edges whether or not an optimization condition, traffic-way-type value(incoming edge)&gt;traffic-way-type path value (incoming-edge)+traffic-way-type value (actual edge), is fulfilled and if it is fulfilled proceeding to step 10 but if it is not fulfilled jumping to step 11; PA1 (10) entering the respective incoming edge in the second list, setting the resistance values of the respective incoming edge in the route table to the sum (path resistance (incoming edge)+resistance (actual edge)), setting the traffic-way-type value of the respective incoming edge in the route table to the sum (traffic-way-type path value (incoming edge)+traffic-way-type value (actual edge)) and entering the actual edge as the following edge of the respective incoming edge and then jumping to step (12); PA1 (11) rejecting the respective incoming edge if PA1 is fulfilled, and when it is fulfilled, entering the respective incoming edge in the second list, setting the resistance value of the respective incoming edge in the route table to the sum (path resistance (incoming edge)+resistance (actual edge)), setting the traffic-way-type value of the respective incoming edge in the route table to the sum (traffic-way-type path value (incoming edge)+traffic-way-type value (actual edge)) and entering the actual edge as the following edge of the respective incoming edge, but when it is not fulfilled rejecting the incoming edge; PA1 (12) setting another edge from the first list as actual edge and going to step (8), or going to step (13) when already all edges contained in the first list were set as the actual edges; and PA1 (13) exchanging the first list with the second list, clearing the second list and jumping to step (6).
At the end of step 1 the following contents result for list II and the route table III: ##STR4##
TABLE III ROUTE +Following -Following Edge +Resistance edge -Resistance edge K.sub.1 .infin. - .infin. - K.sub.2 10 +k.sub.3 .infin. - K.sub.3 0 - 0 - K.sub.4 .infin. - 30 +k.sub.3
Now the lists I and II are exchanged and the list II is empty. Step 2 starts with a new list I with the following contents: ##STR5##
In step 2.1 all incoming-edges for the edge k.sub.2 are tested with the resistance optimization condition, as also illustrated in FIG. 3, and the contents of the route table IV and list II are as follows: ##STR6##
TABLE IV ROUTE +Following -Following Edge +Resistance edge -Resistance edge K.sub.1 20 +k.sub.2 .infin. - K.sub.2 10 +k.sub.3 20 +k.sub.2 K.sub.3 0 - 0 - K.sub.4 40 +k.sub.2 30 +k.sub.3
In the following step 2.2 all incoming-edges for the edge -k.sub.4 are tested with the resistance optimization condition, as illustrated in FIG. 4, and the following contents results for list II and the route table V: ##STR7##
TABLE V ROUTE +Following -Following Edge +Resistance edge -Resistance edge K.sub.1 20 +k.sub.2 .infin. - K.sub.2 10 +k.sub.3 20 +k.sub.2 K.sub.3 0 - 0 - K.sub.4 40 +k.sub.2 30 +k.sub.3
The lists I and II are interchanged and the list II is empty. The next step 3 then begins with a list I with the following contents: ##STR8##
The iteration now takes place step after step until the following route table VI results after termination of the algorithm:
TABLE VI RESULTING ROUTE +Following -Following Edge +Resistance edge -Resistance edge K.sub.1 20 +k.sub.2 30 -k.sub.1 K.sub.2 10 +k.sub.3 20 +k.sub.2 K.sub.3 0 - 0 - K.sub.4 40 +k.sub.2 30 +k.sub.3
Thus according to this route table the edge +k.sub.1 has the following edge +k.sub.2, the edge +k.sub.2 has the following edge +k.sub.3 and the edge +k.sub.3 has no following edge, i.e. the destination has been reached. This determined route is illustrated in FIG. 5 with a dashed arrow.
Frequently a driver is unwilling to travel on express highways or would like to avoid toll roads and/or certain roads because of cost, for example. Also it is conceivable that a driver would like to avoid as much tunnel travel as possible. Up to now calculated routes do not include these considerations or include them only with great effort since they directly increase the resistance values for the respective edges accordingly. However this does not always lead to the desired result, since some edges are essentially cut out from the route by the direct changes of their resistance values. The topography and path guidance may often however lead to no route or only one circuitous route which is very round about which in fact contains none of the excluded types of vehicle paths. Often conventional route determinations end without any results because of the exclusion of too many edges. The opposite can occur also, namely that the computed route leads over an individual excluded edge because the increase of the path resistance of this edge is insufficient. In fact it would be desirable, for example, to only obtain a route with minimal express highway travel distance instead of excluding all edges from the express highway. Also up to now known navigation devices are not in a position to do this.
Furthermore the effect of the path resistances is disadvantageous, since this path resistance can be manipulated for other purposes, especially in traffic telematics. Thus the effect of these methods on the tested routes cannot be predicted.